/*-------------------------------------------------------------------------
 *
 * planagg.c
 *	  聚合查询的特殊规划。
 *
 * 本模块尝试通过子查询替换 MIN/MAX 聚合函数，形式为
 *		(SELECT col FROM tab
 *		 WHERE col IS NOT NULL AND existing-quals
 *		 ORDER BY col ASC/DESC
 *		 LIMIT 1)
 * 给定 tab.col 上的适当索引，这可能比通用的扫描所有行的聚合计划更快。我们可以通过生成多个子查询来处理多个 MIN/MAX 聚合，
 * 其排序可以不同。然而，如果查询包含任何不可优化的聚合，那么就没有意义，因为我们仍然需要扫描所有行。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/plan/planagg.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/htup_details.h"
#include "catalog/pg_aggregate.h"
#include "catalog/pg_type.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/planmain.h"
#include "optimizer/subselect.h"
#include "optimizer/tlist.h"
#include "parser/parse_clause.h"
#include "parser/parsetree.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"

static bool fc_can_minmax_aggs(PlannerInfo *fc_root, List **fc_context);
static bool fc_build_minmax_path(PlannerInfo *fc_root, MinMaxAggInfo *fc_mminfo,
							  Oid fc_eqop, Oid fc_sortop, bool fc_nulls_first);
static void fc_minmax_qp_callback(PlannerInfo *fc_root, void *fc_extra);
static Oid	fc_fetch_agg_sort_op(Oid fc_aggfnoid);


/*
 * preprocess_minmax_aggregates - 预处理MIN/MAX聚合
 *
 * 检查查询是否包含可以通过索引扫描优化的MIN/MAX聚合函数。
 * 如果包含，并且所有聚合都可能是可优化的，则创建MinMaxAggPath并将其添加到
 * (UPPERREL_GROUP_AGG, NULL)上层关系。
 *
 * 在准备调用query_planner()之前，应该由grouping_planner()调用此函数，
 * 因为我们通过克隆规划者的状态并在修改后的查询解析树上调用
 * query_planner()来生成索引扫描路径。因此，在query_planner()之前
 * 需要的所有预处理必须已经完成。这依赖于root->agginfos中的聚合列表，
 * 因此，preprocess_aggrefs()也必须已被调用。
 */
void preprocess_minmax_aggregates(PlannerInfo *fc_root)
{
	Query	   *fc_parse = fc_root->parse;
	FromExpr   *fc_jtnode;
	RangeTblRef *fc_rtr;
	RangeTblEntry *fc_rte;
	List	   *fc_aggs_list;
	RelOptInfo *fc_grouped_rel;
	ListCell   *fc_lc;

	/* 此时minmax_aggs列表应为空 */
	Assert(fc_root->minmax_aggs == NIL);

	/* 如果查询没有聚合，则不需要做任何事情 */
	if (!fc_parse->hasAggs)
		return;

	Assert(!fc_parse->setOperations);	/* 如果是setop则不应该来到这里 */
	Assert(fc_parse->rowMarks == NIL); /* FOR UPDATE时也不应该 */

	/*
	 * 拒绝不可优化的情况。
	 *
	 * 我们不处理GROUP BY或窗口，因为我们当前的
	 * 分组实现无论如何都需要查看所有行，因此
	 * 优化MIN/MAX也没有太大意义。
	 */
	if (fc_parse->groupClause || list_length(fc_parse->groupingSets) > 1 ||
		fc_parse->hasWindowFuncs)
		return;

	/*
	 * 如果查询包含任何CTE，拒绝；没有办法在其上构建索引扫描，
	 * 因此我们无法在这里成功。（如果CTE未被引用，
	 * 那就不是这样，但似乎不值得耗费计算来检查。）
	 */
	if (fc_parse->cteList)
		return;

	/*
	 * 我们还限制查询仅引用一个表，因为连接条件无法合理处理。
	 * （我们也许可以处理包含笛卡尔积连接的查询，但这似乎不值得
	 * 努力。）然而，由于子查询，单个表可能被埋在多个层级的FromExpr中。
	 * 注意，“单个”表也可以是一个继承父类，包括一个已被展平到
	 * appendrel的UNION ALL子查询的情况。
	 */
	fc_jtnode = fc_parse->jointree;
	while (IsA(fc_jtnode, FromExpr))
	{
		if (list_length(fc_jtnode->fromlist) != 1)
			return;
		fc_jtnode = linitial(fc_jtnode->fromlist);
	}
	if (!IsA(fc_jtnode, RangeTblRef))
		return;
	fc_rtr = (RangeTblRef *) fc_jtnode;
	fc_rte = planner_rt_fetch(fc_rtr->rtindex, fc_root);
	if (fc_rte->rtekind == RTE_RELATION)
		 /* 普通关系，可以 */ ;
	else if (fc_rte->rtekind == RTE_SUBQUERY && fc_rte->inh)
		 /* 展平的UNION ALL子查询，可以 */ ;
	else
		return;

	/*
	 * 扫描tlist和HAVING条件以查找所有聚合并验证
	 * 是否都是MIN/MAX聚合。一旦发现一个不是的，则停止。
	 */
	fc_aggs_list = NIL;
	if (!fc_can_minmax_aggs(fc_root, &fc_aggs_list))
		return;

	/*
	 * 好吧，至少有执行优化的可能性。
	 * 为每个聚合构建一个访问路径。如果任何聚合
	 * 证明是不可索引的，则放弃；没有必要只优化
	 * 部分聚合。
	 */
	foreach(fc_lc, fc_aggs_list)
	{
		MinMaxAggInfo *fc_mminfo = (MinMaxAggInfo *) lfirst(fc_lc);
		Oid			fc_eqop;
		bool		fc_reverse;

		/*
		 * 我们需要与聚合的排序操作符相应的相等操作符。
		 */
		fc_eqop = get_equality_op_for_ordering_op(fc_mminfo->aggsortop, &fc_reverse);
		if (!OidIsValid(fc_eqop))	/* 不应该发生 */
			elog(ERROR, "could not find equality operator for ordering operator %u",
				 fc_mminfo->aggsortop);

		/*
		 * 我们可以使用NULLS FIRST或NULLS LAST的排序；此外，
		 * 它们之间不太可能有很大的性能差异，因此如果我们在第一个
		 * 上获得命中，则似乎不值得评估两种方式。NULLS FIRST
		 * 更有可能在操作符是反向排序操作符的情况下可用，因此
		 * 如果是反向的，首先尝试该选项。
		 */
		if (fc_build_minmax_path(fc_root, fc_mminfo, fc_eqop, fc_mminfo->aggsortop, fc_reverse))
			continue;
		if (fc_build_minmax_path(fc_root, fc_mminfo, fc_eqop, fc_mminfo->aggsortop, !fc_reverse))
			continue;

		/* 该聚合没有可索引的路径，因此失败 */
		return;
	}

	
/*
	 * 好的，我们可以这样进行查询。准备创建一个 MinMaxAggPath
	 * 节点。
	 *
	 * 首先，为每个聚合创建一个输出参数节点。（如果最终我们没有
	 * 使用 MinMaxAggPath，我们会为每个聚合浪费一个 PARAM_EXEC 空位，
	 * 这并不值得担心。不幸的是，我们无法等到创建计划时再决定是否
	 * 创建参数。）
	 */
	foreach(fc_lc, fc_aggs_list)
	{
		MinMaxAggInfo *fc_mminfo = (MinMaxAggInfo *) lfirst(fc_lc);

		fc_mminfo->param =
			SS_make_initplan_output_param(fc_root,
										  exprType((Node *) fc_mminfo->target),
										  -1,
										  exprCollation((Node *) fc_mminfo->target));
	}

	/*
	 * 创建一个具有适当估算成本和其他所需数据的 MinMaxAggPath
	 * 节点，并将其添加到 UPPERREL_GROUP_AGG 上层关系中，在那里
	 * 它将与标准聚合实现竞争。（它很可能总是会胜出，但我们在这里
	 * 不需要假设这一点。）
	 *
	 * 注意：grouping_planner 尚未创建这个上层关系，但我们首先创建
	 * 它是没问题的。我们将不会在其中插入正确的 consider_parallel 值，
	 * 但 MinMaxAggPath 路径当前无论如何都永远不安全并行，所以这
	 * 并不重要。同样，我们尚未填充与 FDW 相关的字段也没关系。
	 * 此外，由于没有行标记，我们知道 processed_tlist 不再需要更改，
	 * 所以现在创建 pathtarget 是安全的。
	 */
	fc_grouped_rel = fetch_upper_rel(fc_root, UPPERREL_GROUP_AGG, NULL);
	add_path(fc_grouped_rel, (Path *)
			 create_minmaxagg_path(fc_root, fc_grouped_rel,
								   create_pathtarget(fc_root,
													 fc_root->processed_tlist),
								   fc_aggs_list,
								   (List *) fc_parse->havingQual));
}

/*
 * can_minmax_aggs
 *		遍历查询中的所有聚合，并检查它们是否都是 MIN/MAX 聚合。
 *		如果是，构建树中不同聚合调用的列表。
 *
 * 如果发现非 MIN/MAX 聚合则返回 false，否则返回 true。
 *
 * 这不会深入到子查询中，因此应该仅在将子链接简化为子计划后使用。
 * 也不能有外部聚合引用。
 */
static bool fc_can_minmax_aggs(PlannerInfo *fc_root, List **fc_context)
{
	ListCell   *fc_lc;

	foreach(fc_lc, fc_root->agginfos)
	{
		AggInfo    *fc_agginfo = (AggInfo *) lfirst(fc_lc);
		Aggref	   *fc_aggref = fc_agginfo->representative_aggref;
		Oid			fc_aggsortop;
		TargetEntry *fc_curTarget;
		MinMaxAggInfo *fc_mminfo;

		Assert(fc_aggref->agglevelsup == 0);
		if (list_length(fc_aggref->args) != 1)
			return false;		/* 它不能是 MIN/MAX */

		/*
		 * ORDER BY 对 MIN/MAX 通常不相关，但如果 aggsortop 的操作符类将
		 * 非相同值视为相等，它可能会改变结果。例如，4.0 和 4.00 在
		 * numeric_ops 中是相等的，但可区分。如果 MIN() 接收到多个值
		 * 等于 4.0 且没有小于 4.0 的值，则尚不清楚 MIN() 会返回哪一个
		 * 相等的值。一个对于每个相等值的 ORDER BY 表达式使结果再次可
		 * 预测。这是一个小众需求，我们不通过子查询路径实现它。
		 * 无论如何，这个测试让我们可以快速拒绝有序集合聚合。
		 */
		if (fc_aggref->aggorder != NIL)
			return false;
		/* 注意：我们不在乎是否提到 DISTINCT ... */

		/*
		 * 当存在 FILTER 子句时，我们可能通过将过滤器添加到生成的
		 * 子查询的条件中来实现优化。现在，先放一放。
		 */
		if (fc_aggref->aggfilter != NULL)
			return false;

		fc_aggsortop = fc_fetch_agg_sort_op(fc_aggref->aggfnoid);
		if (!OidIsValid(fc_aggsortop))
			return false;		/* 不是 MIN/MAX 聚合 */

		fc_curTarget = (TargetEntry *) linitial(fc_aggref->args);

		if (contain_mutable_functions((Node *) fc_curTarget->expr))
			return false;		/* 不是潜在可索引的 */

		if (type_is_rowtype(exprType((Node *) fc_curTarget->expr)))
			return false;		/* IS NOT NULL 的语义会很奇怪 */

		fc_mminfo = makeNode(MinMaxAggInfo);
		fc_mminfo->aggfnoid = fc_aggref->aggfnoid;
		fc_mminfo->aggsortop = fc_aggsortop;
		fc_mminfo->target = fc_curTarget->expr;
		fc_mminfo->subroot = NULL; /* 别急着计算路径 */
		fc_mminfo->path = NULL;
		fc_mminfo->pathcost = 0;
		fc_mminfo->param = NULL;

		*fc_context = lappend(*fc_context, fc_mminfo);
	}
	return true;
}

/*
 * build_minmax_path
 *		给定一个 MIN/MAX 聚合，尝试构建一个可以优化的 indexscan Path。
 *
 * 如果成功，则将最佳路径存放在 *mminfo 中并返回 true。
 * 否则，返回 false。
 */
static bool fc_build_minmax_path(PlannerInfo *fc_root, MinMaxAggInfo *fc_mminfo,
				  Oid fc_eqop, Oid fc_sortop, bool fc_nulls_first)
{
	PlannerInfo *fc_subroot;
	Query	   *fc_parse;
	TargetEntry *fc_tle;
	List	   *fc_tlist;
	NullTest   *fc_ntest;
	SortGroupClause *fc_sortcl;
	RelOptInfo *fc_final_rel;
	Path	   *fc_sorted_path;
	Cost		fc_path_cost;
	double		fc_path_fraction;

	/*
	 * 我们将构造一个实际上是子选择查询的内容，因此
	 * 克隆当前查询级别的状态并进行调整，使其看起来
	 * 像一个子查询。任何外部引用现在都将比之前高一个级别。
	 * （这意味着完成后，不会有级别 1 的 Vars，这就是为何子查询
	 * 可以成为 initplan。）
	 */
	fc_subroot = (PlannerInfo *) palloc(sizeof(PlannerInfo));
	memcpy(fc_subroot, fc_root, sizeof(PlannerInfo));
	fc_subroot->query_level++;
	fc_subroot->parent_root = fc_root;
	/* 重置与子计划相关的内容 */
	fc_subroot->plan_params = NIL;
	fc_subroot->outer_params = NULL;
	fc_subroot->init_plans = NIL;
	fc_subroot->agginfos = NIL;
	fc_subroot->aggtransinfos = NIL;

	fc_subroot->parse = fc_parse = copyObject(fc_root->parse);
	IncrementVarSublevelsUp((Node *) fc_parse, 1, 1);

	/* append_rel_list 可能包含外部 Vars 吗？ */
	fc_subroot->append_rel_list = copyObject(fc_root->append_rel_list);
	IncrementVarSublevelsUp((Node *) fc_subroot->append_rel_list, 1, 1);
	/* 目前不应该有任何 OJ 信息需要翻译 */
	Assert(fc_subroot->join_info_list == NIL);
	/* 而且我们也还没有创建等价类 */
	Assert(fc_subroot->eq_classes == NIL);
	/* 而且我们也还没有创建 PlaceHolderInfos */
	Assert(fc_subroot->placeholder_list == NIL);

	/*----------
	 * 生成形式修改后的查询
	 *		(SELECT col FROM tab
	 *		 WHERE col IS NOT NULL AND existing-quals
	 *		 ORDER BY col ASC/DESC
	 *		 LIMIT 1)
	 *----------
	 */
	/* 单个 tlist 条目，即聚合目标 */
	fc_tle = makeTargetEntry(copyObject(fc_mminfo->target),
						  (AttrNumber) 1,
						  pstrdup("agg_target"),
						  false);
	fc_tlist = list_make1(fc_tle);
	fc_subroot->processed_tlist = fc_parse->targetList = fc_tlist;

	/* 没有 HAVING，没有 DISTINCT，聚合不再存在 */
	fc_parse->havingQual = NULL;
	fc_subroot->hasHavingQual = false;
	fc_parse->distinctClause = NIL;
	fc_parse->hasDistinctOn = false;
	fc_parse->hasAggs = false;

	/* 构建 "target IS NOT NULL" 表达式 */
	fc_ntest = makeNode(NullTest);
	fc_ntest->nulltesttype = IS_NOT_NULL;
	fc_ntest->arg = copyObject(fc_mminfo->target);
	/* 我们在 find_minmax_aggs_walker 中检查过它不是行类型 */
	fc_ntest->argisrow = false;
	fc_ntest->location = -1;

	/* 用户可能已经在 WHERE 中包含了它 */
	if (!list_member((List *) fc_parse->jointree->quals, fc_ntest))
		fc_parse->jointree->quals = (Node *)
			lcons(fc_ntest, (List *) fc_parse->jointree->quals);

	/* 构建合适的 ORDER BY 子句 */
	fc_sortcl = makeNode(SortGroupClause);
	fc_sortcl->tleSortGroupRef = assignSortGroupRef(fc_tle, fc_subroot->processed_tlist);
	fc_sortcl->eqop = fc_eqop;
	fc_sortcl->sortop = fc_sortop;
	fc_sortcl->nulls_first = fc_nulls_first;
	fc_sortcl->hashable = false;	/* 不需要使其准确 */
	fc_parse->sortClause = list_make1(fc_sortcl);

	/* 为 LIMIT 1 设置表达式 */
	fc_parse->limitOffset = NULL;
	fc_parse->limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
										   sizeof(int64),
										   Int64GetDatum(1), false,
										   FLOAT8PASSBYVAL);

	/*
	 * 为这个查询生成最佳路径，告知 query_planner 我们
	 * 有 LIMIT 1。
	 */
	fc_subroot->tuple_fraction = 1.0;
	fc_subroot->limit_tuples = 1.0;

	fc_final_rel = query_planner(fc_subroot, fc_minmax_qp_callback, NULL);

	/*
	 * 因为我们没有通过 subquery_planner() 来处理子查询，
	 * 所以我们必须执行一些相同的清理，特别是处理
	 * 在这个子查询中使用的参数和 initplans。 （如果我们最后
	 * 不使用子计划，这不会有什么影响。）
	 */
	SS_identify_outer_params(fc_subroot);
	SS_charge_for_initplans(fc_subroot, fc_final_rel);

	/*
	 * 获取最佳的预排序路径，即仅获取一行时成本最低的路径。
	 * 如果没有这样的路径，则失败。
	 */
	if (fc_final_rel->rows > 1.0)
		fc_path_fraction = 1.0 / fc_final_rel->rows;
	else
		fc_path_fraction = 1.0;

	fc_sorted_path =
		get_cheapest_fractional_path_for_pathkeys(fc_final_rel->pathlist,
												  fc_subroot->query_pathkeys,
												  NULL,
												  fc_path_fraction);
	if (!fc_sorted_path)
		return false;

	/*
	 * 该路径可能无法返回我们想要的确切内容，因此修正它。 （我们
	 * 假设这不会改变对哪个是最便宜路径的结论。）
	 */
	fc_sorted_path = apply_projection_to_path(fc_subroot, fc_final_rel, fc_sorted_path,
										   create_pathtarget(fc_subroot,
															 fc_subroot->processed_tlist));

	/*
	 * 确定获取预排序路径的第一行的成本。
	 *
	 * 注意：此处的成本计算应与
	 * compare_fractional_path_costs() 匹配。
	 */
	fc_path_cost = fc_sorted_path->startup_cost +
		fc_path_fraction * (fc_sorted_path->total_cost - fc_sorted_path->startup_cost);

	/* 保存状态以进行进一步处理 */
	fc_mminfo->subroot = fc_subroot;
	fc_mminfo->path = fc_sorted_path;
	fc_mminfo->pathcost = fc_path_cost;

	return true;
}

/*
 * 在 query_planner() 中计算 query_pathkeys 和其他 pathkeys
 */
static void fc_minmax_qp_callback(PlannerInfo *fc_root, void *fc_extra)
{
	fc_root->group_pathkeys = NIL;
	fc_root->window_pathkeys = NIL;
	fc_root->distinct_pathkeys = NIL;

	fc_root->sort_pathkeys =
		make_pathkeys_for_sortclauses(fc_root,
									  fc_root->parse->sortClause,
									  fc_root->parse->targetList);

	fc_root->query_pathkeys = fc_root->sort_pathkeys;
}

/*
 * 获取与聚合关联的排序操作符的 OID（如果有的话）。
 * 如果没有这样的操作符，则返回 InvalidOid。
 */
static Oid fc_fetch_agg_sort_op(Oid fc_aggfnoid)
{
	HeapTuple	fc_aggTuple;
	Form_pg_aggregate fc_aggform;
	Oid			fc_aggsortop;

	/* 从 pg_aggregate 获取聚合条目 */
	fc_aggTuple = SearchSysCache1(AGGFNOID, ObjectIdGetDatum(fc_aggfnoid));
	if (!HeapTupleIsValid(fc_aggTuple))
		return InvalidOid;
	fc_aggform = (Form_pg_aggregate) GETSTRUCT(fc_aggTuple);
	fc_aggsortop = fc_aggform->aggsortop;
	ReleaseSysCache(fc_aggTuple);

	return fc_aggsortop;
}
